package pers.qianyu.month_202012.date_20201225.dp_bag;

import pers.qianyu.util.*;

/**
 * 798. 背包问题VII
 * https://www.lintcode.com/problem/backpack-vii/description
 * <strong>数量受限的背包求最值问题，可转换为 01 背包问题</strong>
 *
 * @author mizzle rain
 * @date 2020-12-25 15:14
 */
public class BackPackVII {
    public int backPackVII(int n, int[] prices, int[] weight, int[] amounts) {
        int[] dp = new int[n + 1];
        for (int i = 0, len = amounts.length; i < len; i++) {
            int amount = amounts[i];
            for (int j = 0; j < amount; j++) {
                int price = prices[i];
                int w = weight[i];
                for (int k = n; k >= price; k--) {
                    dp[k] = Math.max(dp[k], dp[k - price] + w);
                }
                ArrayUtil.printArrayAsMarkdownTable(
                        String.format("price:%s weight:%s", price, w), dp);
            }
        }
        return dp[n];
    }

    public static void main(String[] args) {
        int n = 8;
        int[] prices = {3, 2};
        int[] weights = {300, 160};
        int[] amounts = {1, 6};
        int result = new BackPackVII().backPackVII(n, prices, weights, amounts);
        System.out.println("result = " + result);
    }
}
